package Demo46;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * 数组中第K个最大的元素
 * https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
 */




class Solution {
    // 快速排序算法 分三块
    public int findKthLargest(int[] nums, int k) {
        func(nums,0,nums.length - 1);
        for(int n:nums) {
            System.out.print(n + "  ");
        }
        return nums[nums.length - k];
    }

    private void func(int[] nums, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int key = nums[new Random().nextInt((end - begin + 1) + begin)];
        int left = begin - 1,right = end + 1;
        for(int i = begin; i < right;i++) {
            if(nums[i] < key) {
                left++;
                swap(nums,left,i);
            }else if(nums[i] > key) {
                right--;
                swap(nums,right,i);
                i--;
            }
        }
        func(nums,begin,left);
        func(nums,right,end);
    }

    private void swap(int[] nums, int left, int i) {
        int tmp = nums[left];
        nums[left] = nums[i];
        nums[i] = tmp;
    }


    // 堆排序
    public int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int n : nums) {
            queue.add(n);
        }
        for(int i = 1; i < k;i++) {
            queue.poll();
        }
        return queue.peek();
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.findKthLargest(new int[] {3,2,3,1,2,4,5,5,6},4);
        System.out.println(ret);
    }
}